CF999E Reachability from the Capital

显然,在一个强联通分量中,只要有一个城市与ss联通,那么整个分量就与ss联通。

于是我们可以缩点,统计它的入度。如果入度为00,我们就从ss向这个缩点连一条边,如果入度不为0,说明其他城市可以到达它,我们就不需要单独连边。

最后,注意特判与ss在同一强联通分量的点。

阅读全文 »

P2831 愤怒的小鸟

首先,我们得知道过原点与两点的抛物线解析式:

设该函数解析式为 y=ax2+bx+c(a<0)y=ax^2+bx+c(a < 0)且过 (0,0),(x1,y1),(x2,y2)(0,0),(x_1,y_1),(x_2,y_2) 三点。

由函数过 (0,0)(0,0)c=0c=0

阅读全文 »

P4778 Counting swaps

对于每个位置 ii , 我们向 pip_i 连一条边。 结合题意可知,一个合法的排列,是一个由 nn 个自环组成的图。

但现在会形成多个环,不妨记环的数量为 kk , 第 ii 个环的大小为 sis_i(包括自环)。

我们现在要做的,就是将这 kk 个环拆成 nn 个自环。

阅读全文 »

SP694 DISUBSTR - Distinct Substrings

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

阅读全文 »